# 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。 
# 
#  
# 
#  示例 1： 
# 
#  
# 输入：s = "bcabc"
# 输出："abc"
#  
# 
#  示例 2： 
# 
#  
# 输入：s = "cbacdcbc"
# 输出："acdb" 
# 
#  
# 
#  提示： 
# 
#  
#  1 <= s.length <= 10⁴ 
#  s 由小写英文字母组成 
#  
# 
#  
# 
#  注意：该题与 1081 https://leetcode-cn.com/problems/smallest-subsequence-of-
# distinct-characters 相同 
# 
#  Related Topics 栈 贪心 字符串 单调栈 👍 1127 👎 0


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        stack = []
        d = {}
        isinstack = set()
        for i in s:
            d[i] = d.get(i, 0) + 1
        """
        思路：利用贪心算法+递增栈，递增栈栈顶元素最大，栈底最小。
        我们对每个字符进行判断，判断是否可以弹出（可以弹出的条件是当前元素比栈顶元素小，且栈顶元素在后续还会出现，因为若栈顶元素后续不出现就弹出那么会改变原来字符串的顺序）
        弹出较大的字符串是为了让较小的字符串尽量的向左（栈里就是向栈底）移动，最后栈里剩下的元素从栈底依次向栈顶展示就是所求
        """
        for i in s:
            # 字符串比较实际是ascll码比较
            if i not in isinstack:
                while stack and i < stack[-1] and d[stack[-1]] > 1:
                    p = stack.pop()
                    # p从栈内移除了,那么对应的set内也应该应该移除
                    isinstack.remove(p)
                    # 此时栈顶元素已经确定被丢弃了,所以-1
                    d[p] -= 1
                stack.append(i)
                isinstack.add(i)
            else:
                d[i] -= 1

        return "".join(stack)


# leetcode submit region end(Prohibit modification and deletion)
Solution().removeDuplicateLetters(s="bbcaac")
